/*
 * In this naive approach, a block is allocated by simply incrementing
 * the brk pointer.  A block is pure payload. There are no headers or
 * footers.  Blocks are never coalesced or reused. Realloc is
 * implemented directly using mm_malloc and mm_free.
 *
 * NOTE TO STUDENTS: Replace this header comment with your own header
 * comment that gives a high level description of your solution.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "Constantine&Jimmy",
    /* First member's full name */
    "Constantine Grantcharov",
    /* First member's email address */
    "constantine.grantcharov@utoronto.ca",
    /* Second member's full name (leave blank if none) */
    "Jimmy (Lei) Ba",
    /* Second member's email address (leave blank if none) */
    "j.ba@utoronto.ca"
};

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
//#define ALIGN(size) (((size)>>3) <<3)

#define SIZE_T_SIZE ALIGN(sizeof(size_t))

/* Tag used to delimit allocated and free memory locations */
typedef struct CHUNK_TAG {
    struct CHUNK_TAG *l; /* pointer to preceding tag */
    struct CHUNK_TAG *r; /* pointer to subsequent tag */
} TAG;

/* freebit manipulation macros */
#define GET_CUR_FREEBIT(header) ( (unsigned)*header &  0x1)
#define SET_CUR_FREEBIT(header) *header=( (unsigned)*header |  0x1)
#define CLR_CUR_FREEBIT(header) *header=( (unsigned)*header & ~0x1)

#define GET_PREV_FREEBIT(header) ( (unsigned)*header &  0x2)
#define SET_PREV_FREEBIT(header) *header=( (unsigned)*header |  0x2)
#define CLR_PREV_FREEBIT(header) *header=( (unsigned)*header & ~0x2)


/* compute memory chunk size */
#define CHUNKSIZE(header) (~0x7 & (unsigned)*header)

/* memory traversing macro */
#define NEXT(header) (int*)((char *)header+CHUNKSIZE(header))
#define PREV_BLOCK(header) (int*)((char *)header-CHUNKSIZE((header-1)))
#define NEXT_FREE(header) (int*)(*(header+1))
//#define BRIDGE_FREE_PTR(prev,next) (prev+1)=next

/* move to or from a header */
#define TO_HEADER(p) ( -2 + (int*)(p) )
#define TO_PTR(p) ((2 + (int*)(p))
#define UPDATE_FOOTER(header,value) ( *(NEXT(header) - 1) = value )

/* segregated list */
#define INDEX(size,index) for(index=-4,size=size+HEADER_SIZE-1;ffs(size);size>>=1,index++)
//#define MIN(X,Y) ((X) < (Y) ? : (X) : (Y))
#define CHK_FREE(index) seg[index]==NULL
#define GET_HEADER(index) seg[index]
#define NEWSIZE(index) 0x1<<(4+index)
#define FIND_FREE(index) for(;seg[index]==NULL && index<19;index++)
#define FIND_FIT(index,size) 
#define REMOVE_ONE(index) seg[index]=(int*)(*(seg[index]+1))
#define ADD_ONE(header_ptr,index) *(header_ptr+1)=(int)seg[index];seg[index]=header_ptr

#define HEADER_SIZE 8
#define SEGREGATED_LIST_SIZE 20
#define MIN_BLOCK_SIZE 16
#define MAX_BLOCK_SIZE 8388600
#define MIN_SIZE 8
#define SEG_LIST_OFFSET 4        

static int* seg[20];

int seg_index( unsigned int size ) {
    unsigned int temp = size;
    int count = 0;
	temp--;
    if( size <=0  ){
        return -1;
    } else if (size < MIN_BLOCK_SIZE ) {
        return 0;
    } else if( size >= MAX_BLOCK_SIZE ) {
        return 20;
    } else {
        if( (size & 0xffff0000) == 0 ) {
            for( ; (temp & 0x0000ffff) != 0; temp = temp>>1, count++ );
        } else {
            for( ; (temp & 0x80000000) == 0; temp = temp<<1, count++ );
            count = 32 - count;
        }

        count = count - SEG_LIST_OFFSET - 1;
        return count;
    }
}

void mm_checker(void)
{
/*
printf("====Begin=====\n\n");
TAG* tag;
for(tag=bot;tag->r!=(TAG*)1;tag=NEXT(tag))
{
printf("================\nheader: %p\n---------------\npayload: %p\nsize: %d\n---------------\n===================\n",tag,(tag+1),CHUNKSIZE(tag));
}

printf("====END=====\n\n");
*/
}
//static TAG *top;
void mm_print_seg(int lower,int upper)
{
	int i,sum,*ptr;
	for(i=lower;i<=upper;i++)
	{
		printf("\n==========\n");
		printf("----%d----",i);
		ptr=seg[i];
		sum=0;
		while(ptr!=NULL)
		{
			printf("->s:%d a:%p",CHUNKSIZE(ptr),ptr);
			ptr=(int *)(NEXT_FREE(prt));
			sum++;
		}
		printf("\nCount:%d",sum);
		
	}
	printf("\n======END=======\n\n\n");
}


/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
	int i;
	for(i=0;i<20;i++)
		seg[i]=NULL;

    return 0;
}

/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size)
{
//	printf("\n******MALLOC(%d)\n",size);
//	printf("\n******BEFORE\n");
//	mm_print_seg(0,8);

	int *header=NULL,*tmp,oldsize=size;
	oldsize = ALIGN(size+8);
//	printf("oldsize: %d\n",oldsize);
	
	register int index,oldindex;

//	if(size>12)
//		index=INDEX(size+4);
//	else
//		index=0;
//	mm_print_seg();
//	printf("old size: %d",size);
	if(size>MIN_SIZE && size< MAX_BLOCK_SIZE)
	{
//		puts("case1");
//		printf("request size: %d",size);

	        INDEX(size,index);
		oldindex=index;

//		printf("\nindex: %d\n",index);

		size=NEWSIZE(index);
		
		while(index<19)
		{
			tmp=header=seg[index];
			int i=0;
//			mm_print_seg(0,8);
			while(header!=NULL)
			{
//				mm_print_seg(0,8);
//				printf("Checking index: %d\n",index);
				if(oldsize<=CHUNKSIZE(header))
				{

//					printf("%p,%p\n",(tmp),header);
//					printf("%d,%d\n",(unsigned)(*(tmp+1)),(unsigned)(*(header+1)));
					if((CHUNKSIZE(header)-oldsize)<16)
					{
//						puts("sub case 1, nothing to splite");
						
						if(NEXT_FREE(header)!=NULL)
						{
							if(i==0)
							{
								*(NEXT_FREE(header)+2)=(int)NULL;
								REMOVE_ONE(index);
							}
							else
							{
								*(tmp+1)=(int)(*(header+1));
								*(NEXT_FREE(header)+2)=(int)tmp;
							}
						}
						else
						{
							if(i==0)
							{
								REMOVE_ONE(index);
							}
							else
							{
								*(tmp+1)=(int)(*(header+1));
							}
						}
							
						*header=oldsize;
						
//						printf("\n******AFTER\n");
//						mm_print_seg(6,8);
//						printf("\n******END MALLOC(%d)\n",size);
						
						
						SET_CUR_FREEBIT(header);
						SET_PREV_FREEBIT(header);

						return (void *)(header + 2);
					}
					else
					{
//						puts("sub case 2, splite the extra pieces from the block on the free list");
//						printf("size: %d index: %d\n",size,index);

//						mm_print_seg(0,8);
//						printf("size: %d addr: %p\nnext blook:%p",CHUNKSIZE(header),header,NEXT(header));
						if(NEXT_FREE(header)!=NULL)
						{
							if(i==0)
							{
								*(NEXT_FREE(header)+2)=(int)NULL;
								REMOVE_ONE(index);
							}
							else
							{
								*(tmp+1)=(int)(*(header+1));
								*(NEXT_FREE(header)+2)=(int)tmp;
							}
						}
						else
						{
							if(i==0)
							{
								REMOVE_ONE(index);
							}
							else
							{
								*(tmp+1)=(int)(*(header+1));
							}
						}
						
						
						
						int tempsize = size=(CHUNKSIZE(header)-oldsize);
//						printf("(CHUNKSIZE(header)-oldsize)-oldsize)=%d\n",(CHUNKSIZE(header)-oldsize));

						INDEX(size,index);
						index--;
//						printf("size: %d index: %d\n",tempsize,index);
						*header=oldsize;

						*(NEXT(header))=tempsize;
						SET_PREV_FREEBIT(NEXT(header));
						*(NEXT(header)+2)=(int)NULL;

						ADD_ONE((NEXT(header)),index);

//						printf("\n******AFTER\n");
//						mm_print_seg(0,6);
//						printf("\n******END MALLOC(%d)\n",size);

						SET_PREV_FREEBIT(header);

						return (void *)(header + 2);
					}
				}
				tmp=header;
				header=NEXT_FREE(header);
				i++;
			}
			tmp=header;
			index++;
			FIND_FREE(index);
		}

//		printf("size: %d\n",oldsize);
//		index++;
//		FIND_FREE(index);

//		printf("new index: %d\n",index);
//		printf("oldsize: %d\n",oldsize);
		
		if(index==19)
		{
//			puts("Create New");
			header=(int*)mem_sbrk(oldsize);
			if ((int)header == -1)
		        	return NULL;
		    
			*header=oldsize;
//			printf("oldsize: %d\n",oldsize);
//			printf("size: %d\n",CHUNKSIZE(header));
		}
		else
		{
					//Splite
			printf("\nSpliting Case1\n");
			
//			mm_print_seg();
			
			header=tmp=seg[index];
			REMOVE_ONE(index);
			
			*header=size;

			for(;oldindex<index;oldindex++)
			{
			
				size=NEWSIZE(oldindex);
				printf("Insert Size: %d\n",size);
				tmp=NEXT(tmp);
				*tmp=size;

				//mm_print_seg(6,9);
				//printf("\n\nInsert Size: %d\n\n",size);
				ADD_ONE(tmp,oldindex);
				//mm_print_seg(6,9);
			}

			if(NEXT(header)!=mem_heap_hi())
			{
				SET_PREV_FREEBIT(NEXT(header));
			}
		}
	}
	else if(size>MAX_BLOCK_SIZE)
	{
//		puts("case2");
        INDEX(size,index);
		size=NEWSIZE(index);

		if((header=GET_HEADER(19))!=NULL)
		{
			tmp=header;
			do
			{
				if(size<CHUNKSIZE(header))
				{
					//tmp=(tmp+1);
					*(tmp+1)=(int)NEXT_FREE(header);
					//Splite
					printf("\nSpliting Case2\n");
					*header=size;

					oldindex=index;
					size=CHUNKSIZE(header);
			   	     	INDEX(size,index);
					
					for(;oldindex<index;oldindex++)
					{
					
						size=NEWSIZE(oldindex);
						printf("Insert Size: %d\n",size);
						tmp=NEXT(tmp);
						*tmp=size;
		
				
						ADD_ONE(tmp,20);
					}
					if(NEXT(header)!=mem_heap_hi())
					{
						SET_PREV_FREEBIT(NEXT(header));
					}


					SET_CUR_FREEBIT(header);
					SET_PREV_FREEBIT(header);
					
				    	return (void *)(header + 2);
					
				}
				tmp=header;
			}
			while((header=NEXT_FREE(header))!=NULL);
		}
		header=(int*)mem_sbrk(size);
		if ((int)header == -1)
	        	return NULL;
	    
		*header=size;
	}
	else
	{
//		printf("\nsize: %d",size);
//		puts("case3");
		index=oldindex=0;
		size=16;
		FIND_FREE(index);
		
		if(index==19)
		{
//			puts("if");
			
			header=(int*)mem_sbrk(size);
			if ((int)header == -1)
		        return NULL;
		    
			*header=size;
		}
		else
		{			
			//Splite
			printf("\nSpliting Case3\n");
			header=tmp=seg[index];
			REMOVE_ONE(index);
			
			*header=size;

			for(;oldindex<index;oldindex++)
			{
			
				size=NEWSIZE(oldindex);
				printf("Insert Size: %d\n",size);
				tmp=NEXT(tmp);
				*tmp=size;

				
				ADD_ONE(tmp,oldindex);
			}

			if(NEXT(header)!=mem_heap_hi())
			{
				SET_PREV_FREEBIT(NEXT(header));
			}
		}
	}
//	printf("\n******AFTER\n");
//	mm_print_seg(6,8);
//	printf("\n******END MALLOC(%d)\n",size);

  	SET_CUR_FREEBIT(header);
	SET_PREV_FREEBIT(header);
	printf("header addr: %p\n", header);
    	return (void *)(header + 2);

}
/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr)
{
	printf("\nFREE(%p, %d) \n\n",TO_HEADER(ptr), CHUNKSIZE(TO_HEADER(ptr)));
//	printf("\n******BEFORE\n");
//	mm_print_seg(6,10);

    int *p, *q;
    int *nxt_header = NULL;
    int index = -1, temp = -1;
    
    p = TO_HEADER(ptr);

    if( !GET_CUR_FREEBIT(p) )
        return;

    printf("p --- ADDR: %p, SIZE: %d, PREV_FREE: %d, CUR_FREE: %d\n", p, CHUNKSIZE(p),GET_PREV_FREEBIT(p), GET_CUR_FREEBIT(p) );
    printf("p --- header value: %x\n", *p);
    printf("free bit for current block cleared!\n");
    
    /* clear free bit for this block's header */
    CLR_CUR_FREEBIT(p);
    printf("p --- ADDR: %p, SIZE: %d, PREV_FREE: %d, CUR_FREE: %d\n", p, CHUNKSIZE(p),GET_PREV_FREEBIT(p), GET_CUR_FREEBIT(p) );
    printf("p --- header value: %x\n", *p);

    /* update header of next block to reflect that previous is free */
    q = NEXT(p);
    printf("q --- ADDR: %p, SIZE: %d, PREV_FREE: %d, CUR_FREE: %d\n", q, CHUNKSIZE(q),GET_PREV_FREEBIT(q), GET_CUR_FREEBIT(q) );
    printf("clearing previous free bit from next block's header\n");
    if( GET_CUR_FREEBIT(q) ) {
	CLR_PREV_FREEBIT(q);
        printf("q --- ADDR: %p, SIZE: %d, PREV_FREE: %d, CUR_FREE: %d\n", q, CHUNKSIZE(q),GET_PREV_FREEBIT(q), GET_CUR_FREEBIT(q) );
    }

    /* copy 4 bytes of header into footer */
    printf("copying header value into footer\n");
    printf("before: footer value: %x\n", *(q-1) );
    memcpy( q-1, p, sizeof(p));
    printf("after: footer value: %x\n", *(q-1) );


    if( !GET_PREV_FREEBIT(p) && CHUNKSIZE(p) > 0 ) { /* consolidate left chunk */
        int previous_bit;
        printf("left block\n");
	temp = CHUNKSIZE(p);
	INDEX( temp, index );
	printf("size: %d ,index: %d\n", CHUNKSIZE(p), index);

        q = PREV_BLOCK(p);
        previous_bit = GET_PREV_FREEBIT(q);
        printf("q --- ADDR: %p, SIZE: %d, PREV_FREE: %d, CUR_FREE: %d\n", q, CHUNKSIZE(q),GET_PREV_FREEBIT(q), GET_CUR_FREEBIT(q) );
        printf("q ---- header value %x\n", *q);
        assert( GET_CUR_FREEBIT(q) == 0 );
        *q = ( CHUNKSIZE(p) + CHUNKSIZE(q) ) | previous_bit;
        printf("q --- ADDR: %p, SIZE: %d, PREV_FREE: %d, CUR_FREE: %d\n", q, CHUNKSIZE(q),GET_PREV_FREEBIT(q), GET_CUR_FREEBIT(q) );
        printf("q --- footer before update: %x\n", *(NEXT(q)-1) );
        UPDATE_FOOTER(q, *q);
        printf("q --- footer after update: %x\n", *(NEXT(q)-1) );

        /* modify next/previous pointers */
        if( (q+1) != NULL || (q+2) != NULL ) {
            int *prv, *nxt;
            prv = (q+1);
            nxt = (q+2);
		printf("prv: %p, nxt: %p\n", prv, nxt);
            *(nxt + 1) = *(q + 1);
            *(prv + 2) = *(q + 2);
        }
        p = q;
    }
    //printf("\nSWITCH(before): p: %p, q: %p\n", p, q);
    q = NEXT(p);
    //printf("SWITCH(after): p: %p, q: %p\n\n", p, q);
    if( !GET_CUR_FREEBIT(q) && CHUNKSIZE(q) > 0) { /* consolidate right chunk */
        assert( GET_CUR_FREEBIT(q) == 0 );
        printf("right block\n");
        printf("q --- ADDR: %p, SIZE: %d, PREV_FREE: %d, CUR_FREE: %d\n", q, CHUNKSIZE(q),GET_PREV_FREEBIT(q), GET_CUR_FREEBIT(q) );
        mm_print_seg(15, 19);
	printf("p ---- header value %x\n", *p);
        *p = ( CHUNKSIZE(p) + CHUNKSIZE(q) ) | GET_PREV_FREEBIT(p);
        printf("p --- ADDR: %p, SIZE: %d, PREV_FREE: %d, CUR_FREE: %d\n", p, CHUNKSIZE(p),GET_PREV_FREEBIT(p), GET_CUR_FREEBIT(p) );
        //printf("p --- footer before update: %x\n", *(NEXT(p)-1) );
        UPDATE_FOOTER(p, *p);
        printf("p --- footer after update: %x\n", *(NEXT(p)-1) );
        
        /* modify next/previous pointers */
        if( (q+1) != NULL || (q+2) != NULL ) {
            int *prv, *nxt;
            prv = (q+1);
            nxt = (q+2);
		printf("prv: %p, nxt: %p\n", prv, nxt);

            *(nxt + 1) = *(q + 1);
	    if( prv != NULL )
            	*(prv + 2) = *(q + 2);
        }
    }
    
    temp = CHUNKSIZE(p);
    INDEX(temp, index);

    nxt_header = seg[index];
    *(p+1) = (int) NULL;
    
    if( nxt_header != NULL ) {
	*(p+2) = (int) nxt_header;
    	*(nxt_header+1) = (int)p;
    }
    seg[index] = p;
    if( seg[index] == seg[index-1] ){
	seg[index-1] = NULL;
    }

	printf("\n******AFTER\n");
	mm_print_seg(6,10);
	printf("\nEND FREE(%p, %d, index = %d) \n\n", p, CHUNKSIZE(p), index);
	
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
	void *oldptr = ptr;
	void *newptr;
	size_t oldsize;
	size_t copySize;
	int index;
	int *header;

	header=(int*)ptr;

	size = ALIGN(size+8);

	oldsize=CHUNKSIZE(TO_HEADER(ptr));
	copySize = CHUNKSIZE(TO_HEADER(ptr))-8;
	mm_print_seg(0,20);
	if(oldsize<size)
	{
		printf("oldsize=%d requested newsize=%d\n",oldsize,size);
		puts("case1");
		newptr=mm_malloc(size);
		if(newptr==NULL)
			return NULL;
		memcpy(oldptr,newptr,copySize);
		mm_free(oldptr);
		return(newptr);
	}
	else if(oldsize >= size && oldsize<(size+16))
	{
		puts("case2");
		return(oldptr);
	}
	else
	{
		puts("case3");
		ptr=TO_HEADER(ptr);

		printf("oldsize=%d requested newsize=%d\n",oldsize,size);
		copySize=size;
		int tmp = (oldsize-size);
		*(header)=size;
		*(NEXT(header))=tmp;

		INDEX(size,index);
		ADD_ONE(NEXT(header),index);

//						printf("\n******AFTER\n");
//						mm_print_seg(0,6);
//						printf("\n******END MALLOC(%d)\n",size);

		SET_PREV_FREEBIT(NEXT(header));
		return(ptr);
	}
/*    
	newptr = mm_malloc(size);
	if (newptr == NULL)
		return NULL;
    copySize = CHUNKSIZE(TO_HEADER(ptr))-SIZE_T_SIZE;
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
*/
}













